package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/10 11:08
 * https://leetcode-cn.com/problems/implement-strstr/
 */
public class Title28 {

    public static int strStr(String haystack, String needle) {
        if ("".equals(needle)) {
            return 0;
        }
        int i = 1, j = 1;
        int s = haystack.length();
        int t = needle.length();
        int[] next = new int[t + 2];
        //初始化next数组
        getNext(needle, next);
        while (i <= s && j <= t) {
            if (j == 0 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j > t) {
            return i - j + 1;
        } else {
            return -1;
        }
    }

    private static void getNext(String t, int[] next) {
        //看成主串i和模式串j的匹配
        int i = 1, j = 0;
        while (j < t.length()) {
            if (j == 0 || t.charAt(i - 1) == t.charAt(j - 1)) {
                i++;
                j++;
                if (t.charAt(i - 1) != t.charAt(j - 1)) {
                    next[i] = j;
                } else {
                    next[i] = next[j];
                }
            } else {
                j = next[j];
            }
        }
    }


    public static void main(String[] args) {
        strStr("abcabcabc","abcabcabc");
    }
}
